package cs6238.server;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.List;
import java.util.Set;
import java.util.UUID;

import cs6238.common.DelegateEntry;
import cs6238.common.FileInfo;

/**
 * I thought about this for a little while, and decided the best way to model the
 * delegates was through a graph.  The nodes of the graph are hosts.  A node can own a set
 * of fileIds.  The edges in the graph are the delegations between nodes.
 * 
 * There are a lot of reasons why this is difficult:
 * - fileIds can be owned by more than one host
 * - delegations can expire
 * - there may be multiple paths to the same file owner
 * - there may be multiple paths to the same fileId on different owners
 * - the graph can include cycles
 * - etc.
 * 
 * I'll probably attach a few graphs to the report to explain the basics of how this works
 * 
 * This is just a search algorithm, and it isn't meant for storing information
 * for any amount of time.  Delegates can expire, and this algorithm doesn't
 * recognize that.  Whenever you want to see what a host can access, take a 
 * snapshot of the current live delegates, and files. Create a new graph, 
 * query it.  Throw the graph away afterwards.
 * 
 * Yes it would be more efficient if a new graph didn't have to be created for each
 * query, but this is a class project not a work project.  This solution is pretty
 * clean, and simple.
 */
public class DelegateGraph {
	
	private List<FileEntry> _fileEntries;
	private List<DelegateEntry> _delegateEntries;
	private Set<String> _hosts;
	private Set<UUID> _fileIds;
	
	private Hashtable<String, HostNode> _hostNodes;
	
	public DelegateGraph(List<FileEntry> fileEntries, List<DelegateEntry> delegateEntries){
		_fileEntries = fileEntries;
		_delegateEntries = delegateEntries;
		
		_hosts = new HashSet<String>();
		_fileIds = new HashSet<UUID>();
		_hostNodes = new Hashtable<String, HostNode>();
		
		for(FileEntry entry : fileEntries){
			_hosts.add(entry.getHostname());
		}
		
		for(DelegateEntry entry : delegateEntries){
			_hosts.add(entry.getDelegatedHost());
			_hosts.add(entry.getOwningHost());
		}
		
		//Add in HostNodes to graph
		for(String host : _hosts){
			HostNode node = new HostNode(host);
			_hostNodes.put(host, node);
		}
		
		//Add all Files to graph
		for(FileEntry file : _fileEntries){
			HostNode node = _hostNodes.get(file.getHostname());
			node.addFileId(file.getFileId());
		}
		
		
		//Add all edges to graph
		for(DelegateEntry delegate : _delegateEntries){
			HostNode endNode = _hostNodes.get(delegate.getOwningHost());
			HostNode startNode = _hostNodes.get(delegate.getDelegatedHost());
			startNode.addDelegationEdge(new DelegationEdge(delegate, endNode));
		}
		
		//Create a set of fileIds
		for(FileEntry file : _fileEntries){
			_fileIds.add(file.getFileId());
		}
	}
	
	/**
	 * For the paranoid
	 */
	public void validateDelegateEntries(){
		ArrayList<DelegateEntry> verifiedDelegateEntries = new ArrayList<DelegateEntry>();
		for(DelegateEntry entry : _delegateEntries){
			if(DelegationVerifier.isDelegationValid(entry)){
				verifiedDelegateEntries.add(entry);
			}
		}
		
		_delegateEntries = verifiedDelegateEntries;
	}
	
	private String getFilenameForFileIdAndHost(String host, UUID fileId){
		for(FileEntry entry : _fileEntries){
			if(entry.getFileId().equals(fileId) && entry.getHostname().equals(host)){
				return entry.getClientFilename();
			}
		}
		
		//This case shouldn't really happen
		return null;
	}
	
	
	/**
	 * OK, so running a separate search for every fileId is not efficient.
	 * BUT! It would be a lot harder to search for all fileIds at once.
	 * @param host
	 * @return
	 */	
	public List<FileInfo> getAllVisibleFiles(String host){
		List<FileInfo> result = new ArrayList<FileInfo>();
	
		for(UUID fileId : _fileIds){
			FileInfo info = doesPathExist(host, fileId);
			if(info != null){
				result.add(info);
			}
		}
		
		return result;
	}
	
	private FileInfo doesPathExist(String host, UUID fileId){
		//clear all visited edges before start
		for(HostNode node : _hostNodes.values()){
			node.clearVisited();
		}
		
		HostNode startNode = _hostNodes.get(host);
		if(startNode == null){
			return null;
		}
		
		return doesPathExist(host, startNode, fileId);
	}
	
	/**
	 * A recursive DFS of graph
	 */
	private FileInfo doesPathExist(String startingHost, HostNode host, UUID fileId){
		if(host.isDestination(fileId)){
			String clientFilename = getFilenameForFileIdAndHost(host.getHost(), fileId);
			return new FileInfo(clientFilename, fileId, host.getHost());
		}
		
		DelegationEdge edge = host.nextValidEdge(startingHost, fileId);
		while(edge != null){
			edge.setVisited(true);
			FileInfo info = doesPathExist(startingHost, edge.getEndPoint(), fileId);
			if(info != null){
				return info;
			}
			edge = host.nextValidEdge(startingHost, fileId);
		}
		
		return null;
	}
	
	
	private class HostNode{
		private String _host;
		private List<DelegationEdge> _outgoingEdges;
		private Set<UUID> _ownedFileIds;
		
		public HostNode(String host){
			_host = host;
			_outgoingEdges = new ArrayList<DelegationEdge>();
			_ownedFileIds = new HashSet<UUID>();
		}
		
		public String getHost(){
			return _host;
		}
		
		public void addDelegationEdge(DelegationEdge edge){
			_outgoingEdges.add(edge);
		}
		
		public void addFileId(UUID fileId){
			_ownedFileIds.add(fileId);
		}
		
		public boolean isDestination(UUID fileId){
			return _ownedFileIds.contains(fileId);
		}
		
		public DelegationEdge nextValidEdge(String startingHost, UUID fileId){
			for(DelegationEdge edge : _outgoingEdges){
				if(edge.isValidForFileId(startingHost, fileId)){
					return edge;
				}
			}
			
			return null;
		}
		
		public void clearVisited(){
			for(DelegationEdge edge : _outgoingEdges){
				edge.setVisited(false);
			}
		}
	}
	
	private class DelegationEdge{
		private DelegateEntry _entry;
		private HostNode _endPoint;
		private boolean _visited;
		
		public DelegationEdge(DelegateEntry entry, HostNode endPoint){
			_entry = entry;
			_endPoint = endPoint;
			_visited = false;
		}
		
		public void setVisited(boolean value){
			_visited = value;
		}
		
		public boolean isValidForFileId(String startingHost, UUID fileId){
			return _entry.getFileId().equals(fileId) 
					&& (!_visited) 
					&& (_entry.getStar() || _entry.getDelegatedHost().equals(startingHost));
		}
		
		public HostNode getEndPoint(){
			return _endPoint;
		}
	}
}
